package com.more.offer.algorithm.sort.sort_05;

import java.util.Arrays;

/**
 * Date: 2020-03-15 23:34
 * Author: pinoc
 * Desc:
 */
public class ShellSort {

	public static void shellSort(int[] array) {
		int length = array.length;
		//gap分组
		for (int gap = length/2; gap > 0; gap = gap/2) {
			for (int i = gap; i < length; i++) {
				int gapValue = array[i];
				while (i - gap >= 0 && array[i - gap] > gapValue) {
					array[i] = array[i - gap];
					i = i - gap;
				}
				array[i] = gapValue;
			}
		}
		//打印每次排序后的结果
		System.out.println(Arrays.toString(array));
	}

	public static void shellSort2(int[] arr) {
		//遍历所有的步长
		for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
			//遍历所有的元素
			for (int i = gap; i < arr.length; i++) {
				//遍历本组中所有元素
				for (int j = i - gap; j >= 0; j -= gap) {
					//如果当前元素大于加上步长后的那个元素
					if (arr[j] > arr[j + gap]) {
						int temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
			//打印每次排序后的结果
			System.out.println(Arrays.toString(arr));
		}
	}

	public static void main(String[] args) {
		int[] arr = {8,5,2,6,1,10,3};
		shellSort2(arr);
	}
}
